#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// 1化之后的字符串
void kmp(string &str, int next[])
{
    next[1] = 0;
    for (int i = 2; i < str.size(); i++)
    {
        int p = next[i - 1];
        while (str[p + 1] != str[i] && p != 0)
            p = next[p];
        next[i] = str[p + 1] == str[i] ? p + 1 : 0;
    }
}